package com.xjj.link;

import java.util.HashMap;
import java.util.Map;

public class M0142LinkedListCycleii {

    public ListNode detectCycle(ListNode head) {

        int index = 0;
        Map<ListNode, Integer> map = new HashMap<>();
        while (head != null) {
            if (!map.containsKey(head)) {
                map.put(head, index);
            } else {
                return head;
            }
            index++;
            head = head.next;
        }
        return null;
    }

    class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }
}
